package mpp;

import java.util.concurrent.atomic.AtomicMarkableReference;

class PQueueImp<T> implements PQueue<T> {
	volatile NodeEx4<T> Head;

	synchronized void printList() {
		NodeEx4<T> node = Head;
		while (node.next.getReference() != null) {
			if (node.next.isMarked())
				System.out.print("(*)" + "Key: " + node.key + "->");
			else
				System.out.print("( )" + "Key: " + node.key + "->");
			node = node.next.getReference();
		}
		System.out.println((node.next.isMarked() ? "(*)" : "( )") + "Key: "
				+ node.key);

	}

	public PQueueImp() {
		super();
		Head =new NodeEx4<T>(null, Integer.MIN_VALUE);
		Head.next.set(new NodeEx4<T>(null, Integer.MAX_VALUE), false);
	}

	private Window<T> find(NodeEx4<T> head, int key){
		NodeEx4<T> pred =null, curr =null, succ =null;
		boolean[] marked = {false};
		boolean snip;
 retry: while(true){
			pred = head;
			curr = pred.next.getReference();
			
			while(true){
				succ = curr.next.get(marked);
				while(marked[0]) {
					snip = pred.next.compareAndSet(curr, succ,false,false);

					if(!snip) 
						continue retry;
					curr = succ;
					succ = curr.next.get(marked);
				}

				if(curr.key >= key)
					return new Window<T>(pred, curr);
				pred = curr;
				curr = succ;
			 }
		 }
	}

	public void add(T item, int score) {
		while (true) {
			Window<T> window = find(Head, score);
			NodeEx4<T> pred = window.pred, curr = window.curr;

			if (curr != null && curr.key == score) {
				// There is an existing node with the same score.
				return;
			} else {
				// Create a new node.
				NodeEx4<T> node = new NodeEx4<T>(item, score);
				node.next = new AtomicMarkableReference<NodeEx4<T>>(curr, false);

				// Special case for the situation where only the Head remains.
				if (pred.next == null) {
					Head.next = new AtomicMarkableReference<NodeEx4<T>>(null,
							false);
					curr.next.compareAndSet(null, node, false, false);
				}

				// Try to update the insertion point to the new node
				// If fails, return the loop.
				else if (pred.next.compareAndSet(curr, node, false, false)) {
					return;
				}
			}
		}
	}

	@Override
	public T removeMin() {
		Boolean snip;
//		printList();
		while (true) {
			Window<T> window = findFirst();
			NodeEx4<T> curr = window.curr;
			if (curr == null) {
				// If the list is empty - return null;
				return null;
			} else {
				// Get the successor.
				NodeEx4<T> succ = curr.next.getReference();

//				System.out.println("Removing: "+curr.key);
				// try to mark the successor as deleted (true)
				snip = curr.next.compareAndSet(succ, succ, false, true);
				
				// If failed to do the previous repeat again.
				if (!snip)
					continue;
				//printList();

				return curr.value;
			}
		}
	}

	private Window<T> findFirst() {
		NodeEx4<T> newNode = Head.next.getReference();

		while (newNode != null && newNode.next.isMarked()) {
			Head.next.compareAndSet(newNode, newNode.next.getReference(),
					false, false);
			newNode = Head.next.getReference();
		}
		return new Window<T>(Head, Head.next.getReference());

		
		
	}

}
